package algdat;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author Mikko Puustinen (mikko.puustinen@gmail.com)
 * @version 0.1, Nov 19, 2007
 */
public class Pilar {
    char[][] arr;
    boolean[][] f;
    List<String> path = new ArrayList<String>(16);

    public void readFile() throws FileNotFoundException {
        File file = new File("pilar.txt");
        Scanner scanner;
        String str = "";
        scanner = new Scanner(new FileReader(file));
        arr = new char[4][4];
        f = new boolean[4][4];

        while (scanner.hasNext()) {
            str += scanner.nextLine();
        }

        int pos = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                arr[i][j] = str.charAt(pos++);
                f[i][j] = false;
            }
        }
    }

    public void solve(int row, int col, int depth) {
        if (depth == 16 && f[0][0]) {
            for (String aPath : path) {
                System.out.print(aPath);
            }
            System.out.println("-------------------");
        } else {
            if (arr[row][col] == 'N') {
                for (int i = 1; i <= row; i++) {
                    if (!f[row - i][col]) {
                        f[row - i][col] = !f[row - i][col];
                        path.add("(" + row + "," + col + ")");
                        solve(row - i, col, depth + 1);
                        path.remove(path.size() - 1);
                    }
                }
            } else if (arr[row][col] == 'S') {
                for (int i = row + 1; i < arr.length; i++) {
                    if (!f[i][col]) {
                        f[i][col] = !f[i][col];
                        path.add("(" + row + "," + col + ")");
                        solve(i, col, depth + 1);
                        path.remove(path.size() - 1);
                    }
                }
            } else if (arr[row][col] == 'E') {
                for (int i = col + 1; i < arr.length; i++) {
                    if (!f[row][i]) {
                        f[row][i] = !f[row][i];
                        path.add("(" + row + "," + col + ")");
                        solve(row, i, depth + 1);
                        path.remove(path.size() - 1);
                    }
                }
            } else if (arr[row][col] == 'W') {
                for (int i = 1; i <= col; i++) {
                    if (!f[row][col - i]) {
                        f[row][col - i] = !f[row][col - i];
                        path.add("(" + row + "," + col + ")");
                        solve(row, col - i, depth + 1);
                        path.remove(path.size() - 1);
                    }
                }
            }

        }
        f[row][col] = !f[row][col];
    }

    public Pilar() {
        try {
            readFile();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        long first = System.currentTimeMillis();
        solve(0, 0, 0);
        long second = System.currentTimeMillis();
        System.out.println("Execution time: " + (second - first) + " ms.");
    }

    public static void main(String[] args) {
        new Pilar();
    }
}
